package common.sort;

/**
 * 原理:
 * 1.选中 pivot 中心轴
 * 2.将大于 pivot 的数字放在 pivot 的右边
 * 3.将小于 pivot 的数字放在 pivot 的左边
 * 4.分别重复以上三个步骤
 */
public class QuickSort01 implements Sort {

    @Override
    public void sort(int[] array) {
        int LEN = array.length;
        quickSort(array, 0, array.length - 1);
    }

    void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }

        int leftIndex = left;
        int rightIndex = right;
        int pivot = array[left];

        while (leftIndex < rightIndex) {
            while (leftIndex < rightIndex && array[rightIndex] >= pivot) {
                rightIndex--;
            }

            if (leftIndex < rightIndex) {
                array[leftIndex] = array[rightIndex];
            }

            while (leftIndex < rightIndex && array[leftIndex] <= pivot) {
                leftIndex++;
            }

            if (leftIndex < rightIndex) {
                array[rightIndex] = array[leftIndex];
            }

            if (leftIndex >= rightIndex) {
                array[leftIndex] = pivot;
            }
        }

        quickSort(array, left, rightIndex - 1);
        quickSort(array, rightIndex + 1, right);
    }
}
